ABC170 D - Not Divisible
問題
コード
公式解説の抜粋
手順
1. 数列$ A_{max}の長さのbool配列 $ dpを用意し、trueで初期化する
$ dp [i] = true のとき、$ i より小さい$ i の約数が$ A に存在しないことを表す
2. 数列の要素を昇順に見て、$ x が数列$ A に含まれているとき、$ x より大きい$ x の倍数$ y について、$ dp[y] をfalseに変更する
同じ値が複数存在する場合に, それらを答えに含めないことに注意する
シミュレーション
code:input
5
24 11 8 3 16
code:py
table = 0 * (A_max + 1) # 0-index => 0 + 1-index # tableのカウントアップ
for x in A:
for y in range(x * 2, A_max + 1, x):
# 結果の集計
result = sum([1 for x in A if tablex == 1]) print(result)
tableのカウントアップ
table:table
x y
3 6
3 9
3 12
3 15
3 18
3 21
3 24
8 16
8 24
11 22
カウントの条件
数列Aの要素x:table[x] += 1
数列Aの要素の倍数(要素は含まない)y: table[y] += 1
table[i] == 1のとき、iより小さいiの約数がAに存在しないことを表す
code:table
0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 2, 0, 1, 0, 0, 1, 1, 0, 3 結果の集計
table:table
table_i 0 0 0 1 0 0 1 0 1 1 0 1 1 0 0 1 2 0 1 0 0 1 1 0 3
i 3 6 8 9 11 12 15 16 18 21 22 24
Aの要素 [3, 8, 11, 16, 24]が1になっているtableの要素の個数を数え上げる
上記の方法でTLEなら 以下の方法をとる
「結果の集計」をやめる
「tableのカウントアップ」時に、数列Aの要素の倍数yはtable[y] = 0とする
解答
初見でできる気がしない……rmaruon.icon
ref